/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-04-23
 * Time: 23:13
 */
/**
 * 单链表实现类
 */
class SinglyLinkedList {
    private ListNode head; // 链表头节点
    private int size;      // 链表长度

    /**
     * 构造方法：初始化空链表
     */
    public SinglyLinkedList() {
        head = null;
        size = 0;
    }

    // ----------------- 基本操作 -----------------

    /**
     * 在链表头部添加节点 --头插法
     * @param val 要添加的值
     */
    public void addAtHead(int val) {
        ListNode newNode = new ListNode(val); // 创建新节点
        newNode.next = head; // 新节点指向原头节点
        head = newNode;      // 更新头节点为新节点
        size++;              // 链表长度加1
    }

    /**
     * 在链表尾部添加节点
     * @param val 要添加的值
     */
    public void addAtTail(int val) {
        if (head == null) {
            addAtHead(val); // 如果链表为空，直接头插，因为这样新节点是头也是尾
            return;
        }

        ListNode current = head;
        // 遍历到最后一个节点（current.next == null）
        while (current.next != null) {
            current = current.next;
        }
        current.next = new ListNode(val); // 尾部插入新节点
        size++;
    }

    /**
     * 在指定索引位置插入节点
     * @param index 插入位置（从0开始）
     * @param val 要插入的值
     */
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return; // 非法索引

        if (index == 0) {
            addAtHead(val);// 插入头部
            return;
        }

        if (index == size) {
            addAtTail(val);// 插入尾部
            return;
        }

        ListNode prev = head;
        // 找到插入位置的前一个节点
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = prev.next; // 新节点指向原位置节点
        prev.next = newNode;      // 前节点指向新节点
        size++;
    }

    /**
     * 删除指定索引位置的节点
     * @param index 要删除的位置
     */
    //法一：
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;

        if (index == 0) {
            head = head.next; // 删除头节点
        } else {
            ListNode prev = head;
            // 找到删除位置的前一个节点
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }
            prev.next = prev.next.next; // 跳过被删除节点
        }
        size--;
    }
    //法二：删除第一次出现关键字为key的节点
    public void remove(int key){
        if(head == null) return;
        if(head.val == key) {
            head = head.next;
            return;
        }
        ListNode prev = findKey(key);
        if(prev == null) {
            return;//没有要删除的数据
        }
        ListNode del = prev.next;
        prev.next = del.next;
     }
     //找删除关键字前一个节点
    private ListNode findKey(int key) {
        ListNode prev = head;
        while(prev.next != null) {
            if(prev.next.val == key) {
                return prev;
            }
            prev = prev.next;
        }
        //没有找到返回null
        return null;
    }


    //删除所有值为key的节点
    public void removeAllKey(int key) {
        if(head == null) return;
        ListNode current = head.next;
        ListNode prev = head;
        while(current!= null) {
            if(current.val == key) {
                prev.next = current.next;
                current = current.next;
            }else {
                prev = current;
                current = current.next;
            }
        }
        if(head.val == key) {
            head = head.next;
        }
    }

    //
    public void clear() {
        ListNode current = head;
        while (current != null) {
            ListNode curN = current.next;
            current.next = null;
            current = curN;
        }
        head = null;
    }


    /**
     * 查找节点是否存在
     * @param val 要查找的值
     * @return 是否存在
     */
    public boolean contains(int val) {
        ListNode current = head;
        while (current != null) {
            if (current.val == val) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    /**
     * 获取链表长度
     * @return 当前链表长度
     */
    public int getSize() {
        return size;
    }

    /**
     * 打印链表内容
     */
    public void printList() {
        ListNode current = head;
        System.out.print("Head -> ");
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}
